package org.example.algorithm.graph;

import java.util.*;

/**
 * 133. 克隆图
 */

public class UndirectedGraphCopySolution {
    private Map<GraphNode, GraphNode> visitedMap = new HashMap<>();

    public static void main(String[] args) {

    }

    //DFS
    public GraphNode cloneGraph(GraphNode node) {
        if (node == null) {
            return null;
        }
        if (visitedMap.containsKey(node)) {
            return visitedMap.get(node);
        }
        GraphNode newNode = new GraphNode(node.val, new ArrayList<>());
        visitedMap.put(node, newNode);
        for (GraphNode neighborNode: node.neighbors) {
            newNode.neighbors.add(cloneGraph(neighborNode));
        }
        return newNode;
    }

    //BFS
    public GraphNode cloneGraphBfs(GraphNode node) {
        if (node == null) {
            return null;
        }
        Map<GraphNode, GraphNode> visited = new HashMap<>();
        Queue<GraphNode> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            GraphNode currentNode = queue.poll();
            if (!visited.containsKey(currentNode)) {
                GraphNode newNode = new GraphNode(currentNode.val, new ArrayList<>());
                visited.put(currentNode, newNode);
            }
            GraphNode cloneNode = visited.get(currentNode);
            for (GraphNode graphNode: currentNode.neighbors) {
                if (!visited.containsKey(graphNode)) {
                    queue.add(graphNode);
                    visited.put(graphNode, new GraphNode(graphNode.val, new ArrayList<>()));
                }
                cloneNode.neighbors.add(visited.get(graphNode));
            }
        }
        return visited.get(node);
    }
}
